package lc.q300_350;

/**
 * 累加数 是一个字符串，组成它的数字可以形成累加序列。
 *
 * 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。
 *
 * 给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
 *
 * 说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
 */
public class Q306 {

    public static void main(String[] args) {
        System.out.println(new Q306().isAdditiveNumber("199001200"));
    }

    public boolean isAdditiveNumber(String num) {
        // 直接暴力解？第一第二位定了，判断后面是
        for (int secondStart = 1; secondStart < num.length() - 1; secondStart++) {
            // 第一位的值是？
            if (num.charAt(0) == '0' && secondStart > 1) {
                break;
            }
            // 第三位的开始
            for (int secondEnd = secondStart; secondEnd < num.length()-1; secondEnd++) {
                // 判断是否正确.第二个数不是0
                if (num.charAt(secondStart) == '0' && secondStart != secondEnd) {
                    break;
                }
                if (valid(secondStart, secondEnd, num)) {
                    return true;
                }
            }
        }
        return false;
    }

    private String plus(String num, Integer firstStart, Integer firstEnd, Integer secondStart, Integer secondEnd) {
        // 数位相加
        StringBuilder third = new StringBuilder();
        int carry = 0;
        int cur = 0;
        while (firstEnd >= firstStart || secondEnd >= secondStart || carry != 0) {
            cur = carry;
            if (firstEnd >= firstStart) {
                // 加上end
                cur += (num.charAt(firstEnd) - '0');
                firstEnd --;
            }
            if (secondEnd >= secondStart) {
                cur += (num.charAt(secondEnd) - '0');
                secondEnd --;
            }
            carry = cur / 10;
            cur %= 10;
            third.append((char) (cur + '0'));
        }
        return third.reverse().toString();
    }

    private boolean valid(int secondStart, int secondEnd, String num) {
        int firstStart = 0, firstEnd = secondStart - 1;
        int n = num.length();
        while (secondEnd <= n - 1) {
            String third = plus(num, firstStart, firstEnd, secondStart, secondEnd);
            int thirdStart = secondEnd + 1;
            int thirdEnd = secondEnd + third.length();
            if (thirdEnd >= n || !num.substring(thirdStart, thirdEnd + 1).equals(third)) {
                break;
            }
            if (thirdEnd == n -1) {
                return true;
            }
            firstStart = secondStart;
            firstEnd = secondEnd;
            secondStart = thirdStart;
            secondEnd = thirdEnd;
        }
        return false;
    }
}
